98. Validate Binary Search Tree
Medium

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A valid BST is defined as follows:

  • The left subtree of a node contains only nodes with keys less than the node's key.
  • The right subtree of a node contains only nodes with keys greater than the node's key.
  • Both the left and right subtrees must also be binary search trees.

 

Example 1:

Input: root = [2,1,3]
Output: true

Example 2:

Input: root = [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's value is 5 but its right child's value is 4.

 

Constraints:

  • The number of nodes in the tree is in the range [1, 104].
  • -231 <= Node.val <= 231 - 1
Accepted
1,018,018
Submissions
3,487,254
Seen this question in a real interview before?

Average Rating: 4.33 (295 votes)

Premium Video

Video Solution


 

Solution Article


Tree definition

First of all, here is the definition of the TreeNode which we would use.




Intuition

On the first sight, the problem is trivial. Let's traverse the tree and check at each step if node.right.val > node.val and node.left.val < node.val. This approach would even work for some trees compute

The problem is this approach will not work for all cases. Not only the right child should be larger than the node but all the elements in the right subtree. Here is an example :

compute

That means one should keep both upper and lower limits for each node while traversing the tree, and compare the node value not with children values but with these limits.


Approach 1: Recursive Traversal with Valid Range

The idea above could be implemented as a recursion. One compares the node value with its upper and lower limits if they are available. Then one repeats the same step recursively for left and right subtrees.

Current
1 / 4

Complexity Analysis

  • Time complexity : O(N)\mathcal{O}(N) since we visit each node exactly once.
  • Space complexity : O(N)\mathcal{O}(N) since we keep up to the entire tree.



Approach 2: Iterative Traversal with Valid Range

The above recursion could be converted into iteration, with the help of an explicit stack. DFS would be better than BFS since it works faster here.

Complexity Analysis

  • Time complexity : O(N)\mathcal{O}(N) since we visit each node exactly once.
  • Space complexity : O(N)\mathcal{O}(N) since we keep up to the entire tree.



Approach 3: Recursive Inorder Traversal

Algorithm

Let's use the order of nodes in the inorder traversal Left -> Node -> Right.

postorder

Here the nodes are enumerated in the order you visit them, and you could follow 1-2-3-4-5 to compare different strategies.

Left -> Node -> Right order of inorder traversal means for BST that each element should be smaller than the next one.

Hence the algorithm with O(N)\mathcal{O}(N) time complexity and O(N)\mathcal{O}(N) space complexity could be simple:

  • Compute inorder traversal list inorder.

  • Check if each element in inorder is smaller than the next one.

postorder

Do we need to keep the whole inorder traversal list?

Actually, no. The last added inorder element is enough to ensure at each step that the tree is BST (or not). Hence one could merge both steps into one and reduce the used space.

Code

We can implement the algorithm recursively.

Complexity Analysis

  • Time complexity : O(N)\mathcal{O}(N) in the worst case when the tree is a BST or the "bad" element is a rightmost leaf.

  • Space complexity : O(N)\mathcal{O}(N) for the space on the run-time stack.




Approach 4: Iterative Inorder Traversal

Alternatively, we could implement the above algorithm iteratively.

Complexity Analysis

  • Time complexity : O(N)\mathcal{O}(N) in the worst case when the tree is BST or the "bad" element is a rightmost leaf.

  • Space complexity : O(N)\mathcal{O}(N) to keep stack.

Report Article Issue

Comments: 130
neeraj_seth's avatar
Read More

Other approach to solve this problem would be to use inorder traversal properties where previous element in output would always be lesser than the current output.

225
Show 2 replies
Reply
Share
Report
durumu's avatar
Read More

Heaps definitely aren't "usually implemented as binary search trees." They're usually implemented as flat arrays.

61
Show 6 replies
Reply
Share
Report
fudonglai's avatar
Read More

Share a concise solution, 5 lines

bool isValidBST(TreeNode* root, TreeNode* min=NULL, TreeNode* max=NULL) {
        if (!root) return true;
        if (min != NULL && root->val <= min->val) return false;
        if (max != NULL && root->val >= max->val) return false;
        return isValidBST(root->left, min, root) && isValidBST(root->right, root, max);
    }

103
Show 11 replies
Reply
Share
Report
lucasmonsteer's avatar
Read More

Just curisou, why BFS is slower than DFS?

39
Show 11 replies
Reply
Share
Report
iguluasg's avatar
Read More

Something recursive here:

class Solution {
    public boolean isValidBST(TreeNode root) {
        return checkNode(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
    
    private boolean checkNode(TreeNode node, long min, long max) {
        if (node == null){
            return true;
        }
        if(node.val > min && node.val < max){
            return (checkNode(node.left, min, node.val) && checkNode(node.right, node.val, max));
        } else {
            return false;
        }
    }
}

19
Show 6 replies
Reply
Share
Report
v1s1on's avatar
Read More

The iterative solution is unnecessarily complicated. You can leverage the fact that an in-order traversal for a BST yields a monotonically increasing sequence. Obviously, it's the same asymptotic complexity but the code is much shorter & easier to follow (IMHO):

 bool isValidBST(TreeNode* root) {
        if (root == nullptr) return true;
        
        stack<TreeNode*> s;
        TreeNode* current = root; TreeNode* prev = nullptr;
        while (current || !s.empty())
        {
            while(current)
            {
                s.push(current);
                current = current->left;
            }
            
            current = s.top(); s.pop();
            if (prev && prev->val >= current->val) return false;
            prev = current;
            current = current->right;
        } 
        return true;
    }

25
Show 4 replies
Reply
Share
Report
jianchao-li's avatar
Read More

The Java code of the first recursive solution can be simplified.

class Solution {
    private boolean isBSTHelper(TreeNode node, long lower_limit, long upper_limit) {
        if (node == null) {
            return true;
        }
        if (node.val <= lower_limit || upper_limit <= node.val) {
            return false;
        }
        return isBSTHelper(node.left, lower_limit, node.val) && isBSTHelper(node.right, node.val, upper_limit);
    }
    public boolean isValidBST(TreeNode root) {
        return isBSTHelper(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
}

33
Show 6 replies
Reply
Share
Report
granola's avatar
Read More

I think, In the first approach, space will be O(h).
My recursive solution:
Time complexity O(N)
Space complexity O(h)

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        return self.checkIfValid(root, -2**32, 2**32)
    
    def checkIfValid(self, root, minRange, maxRange):
        if not root:
            return True
        if minRange >= root.val or maxRange <= root.val:
            return False
        return self.checkIfValid(root.left, minRange, root.val) and self.checkIfValid(root.right, root.val, maxRange)

28
Show 6 replies
Reply
Share
Report
Phatlobster's avatar
Read More

Anyone know why double inorder = - Double.MAX_VALUE instead of int inorder = -Integer.MIN_VALUE

14
Show 3 replies
Reply
Share
Report
silvia0818's avatar
Read More

Why in Approach 1: Recursion, the Space complexity is O(N)? I think no other auxiliary space is needed?

6
Show 6 replies
Reply
Share
Report
Time Submitted
Status
Runtime
Memory
Language
06/03/2021 19:49Accepted24 ms21.7 MBcpp
05/31/2021 20:24Accepted28 ms21.6 MBcpp
05/31/2021 20:23Wrong AnswerN/AN/Acpp
05/31/2021 20:22Runtime ErrorN/AN/Acpp
04/28/2021 12:06Accepted8 ms21.5 MBcpp
06/18/2020 08:50Accepted20 ms21.5 MBcpp
06/05/2020 09:07Accepted20 ms21.5 MBcpp
06/05/2020 09:00Runtime ErrorN/AN/Acpp
/23
Your previous code was restored from your local storage.Reset to default
Contribute
|||
Saved
Trie
This list is empty.